package com.sicheng.lc.lc笔试.百度篇;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/4/25 23:03
 */
public class 长k和偶的序列 {
    /**
     * 有 n 个正整数，
     * 问其中长为 k、和为偶数的子序列有多少个？
     * 子序列就是 k 个位置不同的数组成的序列，但不需要相连。
     */

    public static void main(String[] args) {
    }

    private static final int N = 1000;
    static long[][] dp = new long[N + 1][N + 1];


    static {
        dp[0][0] = 1;
        for (int i = 1; i <= N; i++) {
            dp[i][0] = 1;
            for (int j = 1; j <= N; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
            }
        }
    }

    long cnt(int cnt0, int cnt1, int k) {
        long res = 0;
        for (int i = 2; i <= cnt1; i += 2) {
            if (cnt0 - (k - i) >= 0) {
                res += (long) i * (k - i);
            }
        }

        if (cnt0 >= k) {
            res += dp[cnt0][k];
        }
        if (cnt1 >= k && k % 2 == 0) {
            res += dp[cnt1][k];
        }
        return res;
    }
}
